package stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/29 9:36
 * @description: 给定s和t两个字符串，当它们分别被输入到空白的文本编辑器后，
 * 如果两者相等，返回true，#代表退格字符
 */
public class Backspace {
    public boolean backspaceCompare(String s, String t) {

        int len1 = s.length();
        int len2 = t.length();
        Deque<Character> stack1 = new LinkedList<Character>();
        Deque<Character> stack2 = new LinkedList<Character>();

        for(int i = 0;i<len1;i++){
            if(s.charAt(i) == '#')
            {
                if(stack1.isEmpty()){
                    continue;
                }else{
                    stack1.pop();
                    continue;
                }

            }
            stack1.push(s.charAt(i));
        }
        for(int i = 0;i<len2;i++){
            if(t.charAt(i) == '#' ){
                if(stack2.isEmpty()){
                    continue;
                }else{
                    stack2.pop();
                    continue;
                }
            }
            stack2.push(t.charAt(i));
        }
        if(stack1.size()!=stack2.size()){
            return false;
        }else if(stack1.size()==0){
            return true;
        }
        else{
            while(!stack1.isEmpty()){
                if(stack1.pop()!=stack2.pop()){
                    return false;
                }
            }
        }
        return true;

    }
}
